package com.fjl.list.leetcode0202;

import com.fjl.list.ListNode;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/13 17:33
 */
public class ReturnKthToLast {
    public static void main(String[] args) {

    }

    // 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
    public int kthToLast(ListNode head, int k) {
        ListNode p1 = head, p2 = head;
        // 先让p1走k步,那么p1离链尾的null就剩n-k步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }

        // 这时候p1,p2一起走，p1 走到链表末尾的空指针时前进了 n - k 步，
        // p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        return p2.val;
    }
}
